import javafx.scene.chart.ValueAxis;

/**
 * @Date：2024/12/24
 * @Author：Mr.王亚栋
 * @Version:1.0
 * @Description:
 * @return：
 */
public class LinkedList {

    @Override
    public String toString() {
        return "LinkedList{" +
                "head=" + head +
                '}';
    }

    private Node head;  // 头结点

    // 节点类
    static class Node {
        int val;
        Node next;

        // 构造函数
        public Node(int val) {
            this.val = val;
            this.next = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    // 构造函数，初始化头结点
    public LinkedList() {
        head = new Node(-1);  // 头结点的值一般是0或者其他占位符
    }

    // 插入元素到链表尾部
    public void appendTail(int data) {

        Node newNode = new Node(data);

        // 找到一个指针指向头结点
        Node current = this.head;

        while (current.next != null){

            current = current.next;
        }

        current.next = newNode;

    }

    /**
     * 打印链表
     */
    public void printLinkList() {
        Node curr = head.next;

        while (curr != null)
        {
            System.out.print(curr.val + " ");

            curr = curr.next;
        }
    }

    /**
     * 在头部插入节点
     * @param val
     */
    public void appendHead(int val){

        Node newNode = new Node(val);

        // 新节点地址域指向之前头节点的下一个节点
        newNode.next = head.next;

        // 头结点的地址域指向新生成的节点
        head.next = newNode;

    }

    /**
     * 根据val删除节点
     * @param val
     */
    public void removeLink1(int val){

        // 一个临时节点指向头结点
        Node temp = head;

        while (temp != null && temp.next != null){

            // 如果下一个节点的值等于目标值
            if (temp.next.val == val){

                temp.next = temp.next.next;
                return;

            }

            temp = temp.next;
        }

    }

    /**
     * 使用两个变量来删除节点
     * @param val
     */
    public void removeLink2(int val){

        // 一个临时节点指向头结点
        Node prev = head;
        Node curr = head.next;

        while ( curr != null){

            // 如果下一个节点的值等于目标值
            if (curr.val == val){

                // 前一个节点要指向下一个节点的地址域
                prev.next = curr.next;
                return;

            }

            // 前一个节点后移
            prev = curr;
            // 当前节点后移
            curr = curr.next;
        }

    }

    /**
     * 删除val值相同的多个节点
     * @param val
     */
    public void removeLinkAll(int val){

        Node prev = head;
        Node curr = head.next;

        while ( curr != null){

            if (curr.val == val){

                // 删除这个节点
                prev.next = curr.next;
            }

            prev = curr;
            curr = curr.next;
        }
    }

    /**
     * 查找元素是否在该链表中
     * @param val
     * @return
     */
    public boolean findVal(int val){

        Node curr = head.next;

        while (curr != null){

            if (curr.val == val){

                return true;
            }

            curr = curr.next;
        }
        return false;
    }

    /**
     * 反转一个链表
     * @param list
     */
    public Node reserveLink(LinkedList list){

        Node curr = list.head;

        // 前面一个指针变量prev
        Node prev = null;
        // 后面一个指针变量nextNode
        Node nextNode = null;

        // System.out.println(" *"+nextNode);

        while (curr.next != null){

            // System.out.println(" _"+nextNode);

            // 讲next指针指向当前节点的后面
            nextNode = curr.next;

            curr.next = prev;

            // System.out.println(" _"+prev);

            // 移动 prev 和 nextNode
            prev = curr;
            curr = nextNode;

        }

        return prev;
    }
}
